package com.lw.leetcode.dp.c;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 514. 自由之路
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/9 14:57
 */
public class FindRotateSteps {

    public static void main(String[] args) {
        FindRotateSteps test = new FindRotateSteps();

        // 4
//        String a = "godding";
//        String b = "gd";

        // 13
//        String a = "godding";
//        String b = "godding";

        // 199
        String a = "wegsghrfepwfdknfbieoyiojdhjnnzjsjeiwrjengdfadmfnjewqodgjfklrjrknsdkwruopkjhgderjdkelfkhjdndjfgjeirej";
        String b = "wegsghrfepwfdknfbieoyiojdhjnnzjsjeiwrjengdfadmfnjewqodgjfklrjrknsdkwruopkjhgderjdkelfkhjdndjfgjeirej";

        int rotateSteps = test.findRotateSteps(a, b);
        System.out.println(rotateSteps);
    }

    private char[] arr;
    private int[] counts;
    private int[] counts2;
    private int n;
    private List<Integer>[] lists = new ArrayList[26];

    public int findRotateSteps(String ring, String key) {
        n = ring.length();
        arr = ring.toCharArray();
        counts = new int[n];
        counts2 = new int[n];
        for (int i = 0; i < 26; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            lists[arr[i] - 'a'].add(i);
        }
        for (int i = key.length() - 1; i >= 0; i--) {
            char c = key.charAt(i);
            find(c);
        }
        return counts[0];
    }

    private void find(char c) {
        List<Integer> list = lists[c - 'a'];
        for (int i = 0; i < n; i++) {
            int min = Integer.MAX_VALUE;
            for (int v : list) {
                int t = Math.abs(v - i);
                min = Math.min(min, Math.min(t, n - t) + counts[v] + 1);
            }
            counts2[i] = min;
        }
        System.arraycopy(counts2, 0, counts, 0, n);
    }


}
